1. Field of the Invention
The present invention relates to an error correction circuit, and more specifically to an error correction circuit for correcting errors in polynomial symbols.
2. Description of Related Art
Heretofore, three typical error correction circuits have been proposed. One of the typical error correction circuits is composed of a microprocessor system including a general purpose microprocessor adapted to execute, in accordance with predetermined programs, various operations such as an operation of Galois field in the process of error correction.
A second error correction circuit is composed of a single purpose hardware including one set of a Galois field multiplying circuit and a Galois field adding circuit. Referring to FIG. 1, there is shown a typical example of such a correction circuit, which includes a multiplier 100 coupled to a bus 102 and an adder 104 having one input connected to an output of the multiplier 100 and another input coupled to the bus 102. An output of the adder 104 is also coupled to the bus 102. Further, a memory 106 and a syndrome generator 108 are coupled to the bus 102, and a microprogram control unit 110 is coupled through a unitary delay element 112 to the bus 102.
A third typical error correction circuit is constituted of a systolic array, as shown in FIG. 2. The shown systolic array including a syndrome generator 200, an error position polynominal calculation circuit 202, an error position calculation circuit 204, an error pattern calculation circuit 206 and an error correction circuit 208, which are coupled in cascade.
However, the above mentioned error correction circuits have the following drawbacks, respectively.
Specifically, in the case that an error correction is effected by using a microprocessor system, it is necessary to execute operations such as multiplication of a Galois field in the process of error correction. However, if the multiplication of the Galois field and similar operations are performed by the general purpose microprocessor, it needs a long execution time. In most cases, it entails about ten times the time of a single purpose hardware.
The single purpose hardware including one set of a Galois field multiplication circuit and a Galois field addition circuit as shown in FIG. 1 can have a processing speed higher than the above microprocessor system. However, the processing speed is not sufficient if it is used in a high speed transmission such as a digital video transmission. Therefore, this cannot be applied to a high speed transmission system.
On the other hand, the systolic array as shown in FIG. 2 can have a sufficiently high processing speed, and therefore, can be used in a high speed transmission system. However, this needs a large scale of circuit, and therefore, it is difficult to assemble the circuit on an integrated circuit.